#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<unordered_map>
#include<vector>
#include<string>
using namespace std;

struct ListNode {
    int val;
    struct ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
    
};

ListNode* reverseBetween(ListNode* head, int m, int n) {
    ListNode* res = new ListNode(-1);
    res->next = head;

    ListNode* prev = res;
    ListNode* cur = head;
    for (int i = 1; i < m; ++i)
    {
        prev = cur;
        cur = cur->next;
    }
    for (int i = m; i < n; ++i)
    {
        ListNode* tmp = cur->next;
        cur->next = tmp->next;
        tmp->next = prev->next;
        prev->next = tmp;
    }
    return res->next;
}

ListNode* removeZeroSumSublists(ListNode* head) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    int prefix = 0;
    unordered_map<int, ListNode*> seen;
    for (ListNode* cur = dummy; cur; cur = cur->next)
    {
        prefix += cur->val;
        seen[prefix] = cur;
    }
    prefix = 0;
    for (ListNode* cur = dummy; cur; cur = cur->next)
    {
        prefix += cur->val;
        cur->next = seen[prefix]->next;
    }
    return dummy->next;
}

vector<int> findSubstring(string s, vector<string>& words) {
    unordered_map<string, int> hash1;
    for (auto e : words) ++hash1[e];
    int n = words[0].size(), m = words.size();
    vector<int> ret;
    for (int i = 0; i < n; ++i)
    {
        unordered_map<string, int> hash2;
        int cnt = 0;
        for (int left = i, right = i; right + n <= s.size(); right += n)
        {
            string in = s.substr(right, n);
            ++hash2[in];
            if (hash2[in] <= hash1[in]) ++cnt;
            if (right - left + 1 > n * m)
            {
                string out = s.substr(left, n);
                if (hash2[out] <= hash1[out]) --cnt;
                --hash2[out];
                left += n;
            }
            if (cnt == m) ret.push_back(left);
        }
    }
    return ret;
}

int main()
{
    vector<string> v = { "aa","aa" };
    findSubstring("aaaaaaaaaaaaaa",v);
}